package com.leetcode.LeetCode精选TOP面试题;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @author 覃国强
 * @date 2022-06-30 17:04
 */
public class 题库_0149_直线上最多的点数 {

  public static void main(String[] args) {
    int[][] points = {{0,0},{4,5},{7,8},{8,9},{5,6},{3,4},{1,1}};
    Solution solution = new Solution();
    int maxPoints = solution.maxPoints(points);
    System.out.println(maxPoints);
  }
  
  
  static
  class Solution {
    public int maxPoints(int[][] points) {
      int answer = 1;
      for (int i = 0; i < points.length; ++i) {
        if (answer > points.length / 2 || answer > points.length - i) {
          break;
        }

        Map<Slope, Integer> map = new HashMap<>();
        for (int j = i + 1; j < points.length; ++j) {
          Slope slope = new Slope(points[i], points[j]);
          map.merge(slope, 1, Integer::sum);
        }

        for (Map.Entry<Slope, Integer> entry : map.entrySet()) {
          answer = Math.max(answer, entry.getValue() + 1);
        }
      }

      return answer;
    }

    static class Slope {

      int startX;
      int startY;

      int deltaX;
      int deltaY;

      Slope(int[] point1, int[] point2) {
        startX = point1[0];
        startY = point1[1];
        if (point1[0] > point2[0]) {
          deltaX = point1[0] - point2[0];
          deltaY = point1[1] - point2[1];
        } else {
          deltaX = point2[0] - point1[0];
          deltaY = point2[1] - point1[1];
        }

        if(deltaX != 0 && deltaY != 0) {
          int gcd = gcd(deltaX, deltaY);
          deltaX /= gcd;
          deltaY /= gcd;
        } else if(deltaX == 0 && deltaY != 0) {
          deltaY = 1;
        } else if (deltaX != 0 && deltaY == 0) {
          deltaX = 1;
        }
      }

      private int gcd(int x, int y) {
        return x % y == 0 ? y : gcd(y, x % y);
      }

      @Override
      public boolean equals(Object o) {
        if (this == o) {
          return true;
        }
        if (o == null || getClass() != o.getClass()) {
          return false;
        }
        Slope slope = (Slope) o;
        return startX == slope.startX && startY == slope.startY && deltaX == slope.deltaX && deltaY == slope.deltaY;
      }

      @Override
      public int hashCode() {
        return Objects.hash(startX, startY, deltaX, deltaY);
      }
    }

  }

}
